﻿/**
 * @file std_comm.inl
 * Copyright (c) 2019 Gaaagaa. All rights reserved.
 * 
 * @author  : Gaaagaa
 * @date    : 2019-09-09
 * @version : 1.0.0.0
 * @brief   : 定义 双端队列 内部的相关数据类型、常量、宏 等。
 */

/**
 * The MIT License (MIT)
 * Copyright (c) Gaaagaa. All rights reserved.
 * 
 * Permission is hereby granted, free of charge, to any person obtaining a copy of
 * this software and associated documentation files (the "Software"), to deal in
 * the Software without restriction, including without limitation the rights to
 * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
 * of the Software, and to permit persons to whom the Software is furnished to do
 * so, subject to the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included in all
 * copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
 * FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR
 * COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
 * IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */

#ifndef __STD_DEQUE_INL__
#define __STD_DEQUE_INL__

#ifndef __STD_DEQUE_H__
#error "Please include std_deque.h before this file."
#endif // __STD_DEQUE_H__

#include "std_comm.inl"

////////////////////////////////////////////////////////////////////////////////
// xstd_deque_t 的相关数据类型

/**
 * 定义 节点索引 类型：node position, 
 * 意为 元素节点在 分块 中的偏移量
 */
typedef xdeq_size_t   xdeq_npos_t;

/**
 * 定义 分块索引 类型：chunk position,
 * 意为 分块节点在 分块映射数组 中的偏移量
 */
typedef xdeq_size_t   xdeq_cpos_t;

/**
 * 定义 绝对索引 类型：vector position, 
 * 其值为 [ 分块索引 * 分块大小 + 节点索引 ]
 */
typedef xdeq_size_t   xdeq_vpos_t;

/**
 * 定义 偏移量索引 类型：offset position,
 * 其运算关系 [ 绝对索引 = 偏移量索引 + 首节点的绝对索引 ]
 */
typedef xdeq_size_t   xdeq_opos_t;

/** 定义 用于 元素节点 的指针类型 */
typedef xdeq_elem_t   xdeq_nptr_t;

/** 定义 分块 的指针类型 */
typedef xdeq_nptr_t   xdeq_cptr_t;

/** 定义 分块映射数组 的指针类型 */
typedef xdeq_cptr_t * xdeq_pptr_t;

/**
 * @struct xdeq_node_t
 * @brief  双端队列容器所存储的 节点元素对象 的结构体描述信息。
 */
typedef struct xdeq_node_t
{
    xstd_byte_t     xdeq_elem[0]; ///< 指向节点元素对象的缓存
} xdeq_node_t;

/**
 * @struct xstd_deque_t
 * @brief  双端队列容器的结构体描述信息。
 */
typedef struct xstd_deque_t
{
    xstd_context_t  xstd_ectxt; ///< 节点类型的上下文描述信息

    xdeq_size_t     xchk_size;  ///< 每个元素存储分块的容量（取值为 2^N ）
    xdeq_size_t     xmax_size;  ///< 容器最大可存储的 节点数量
    xdeq_size_t     xdeq_size;  ///< 当前存储的元素 节点数量

    /**
     * 用于交换操作的备用分块 : 
     * 其用于暂存替换下来的内存块，若再次申请内存块时，
     * 优先使用该缓存块，减少系统调用方式的内存申请操作。
     */
    xdeq_cptr_t     xchk_rptr;

    xdeq_vpos_t     xmap_bpos;  ///< 存储 首端节点元素 的 绝对索引 值
    xdeq_vpos_t     xmap_maxv;  ///< 最大的 绝对索引 值（即 xmap_size * xchk_size - 1）
    xdeq_size_t     xmap_size;  ///< 元素存储分块映射数组的 大小（取值为 2^N ）
    xdeq_pptr_t     xmap_pptr;  ///< 元素存储分块映射数组
} xstd_deque_t;

////////////////////////////////////////////////////////////////////////////////
// xstd_deque_t 的相关操作宏函数

//====================================================================

#define XDEQ_ECTXT(xdeq_this)   XSTD_ECTXT(xdeq_this)
#define XDEQ_ETYPE(xdeq_this)   XSTD_ETYPE(xdeq_this)
#define XDEQ_ESIZE(xdeq_this)   XSTD_ESIZE(xdeq_this)
#define XDEQ_ALTOR(xdeq_this)   XSTD_ALTOR(xdeq_this)

#define XDEQ_MALLOC(xdeq_this, xst_size)            \
            XSTD_MALLOC((xdeq_this), (xst_size))

#define XDEQ_DEALLOC(xdeq_this, xmt_mptr)           \
            XSTD_DEALLOC((xdeq_this), (xmt_mptr))

#define XDEQ_ALFROM(xdeq_this, xet_dptr, xet_sptr)  \
            XSTD_ALFROM((xdeq_this), (xet_dptr), (xet_sptr))

#define XDEQ_ALMOVE(xdeq_this, xet_dptr, xet_sptr)  \
            XSTD_ALMOVE((xdeq_this), (xet_dptr), (xet_sptr))

#define XDEQ_ALDEST(xdeq_this, xet_elem)            \
            XSTD_ALDEST((xdeq_this), (xet_elem))

#define XDEQ_ISSAME_TYPE(xdeq_lthis, xdeq_rthis)    \
            XSTD_ISSAME_TYPE((xdeq_lthis), (xdeq_rthis))

#define XDEQ_ECTXT_UPDATE(xdeq_this, xdeq_ctxt)     \
            XSTD_ECTXT_UPDATE((xdeq_this), (xdeq_ctxt))

//====================================================================

#define XDEQ_MAX_SIZE(xdeq_this)     ((xdeq_this)->xmax_size)
#define XDEQ_MIN_MAPSIZE(xdeq_this)  8
#define XDEQ_MAX_MAPSIZE(xdeq_this)  \
    (XDEQ_MAX_SIZE(xdeq_this) / (xdeq_this)->xchk_size)

#define XDEQ_VPOS(xdeq_this, xdeq_opos) \
    ((xdeq_vpos_t)(((xdeq_opos) +       \
                    (xdeq_this)->xmap_bpos) & (xdeq_this)->xmap_maxv))

#define XDEQ_CPOS(xdeq_this, xdeq_opos)                         \
    ((xdeq_cpos_t)(((((xdeq_opos) + (xdeq_this)->xmap_bpos) &   \
                     (xdeq_this)->xmap_maxv) / (xdeq_this)->xchk_size)))

#define XDEQ_NPOS(xdeq_this, xdeq_opos) \
    ((xdeq_npos_t)(((xdeq_opos) +       \
                    (xdeq_this)->xmap_bpos) & ((xdeq_this)->xchk_size - 1)))

#define XDEQ_BEGIN(xdeq_this)  ((xdeq_opos_t)(0))
#define XDEQ_END(xdeq_this)    ((xdeq_opos_t)((xdeq_this)->xdeq_size))
#define XDEQ_RBEGIN(xdeq_this) ((xdeq_opos_t)((xdeq_this)->xdeq_size - 1))
#define XDEQ_REND(xdeq_this)   ((xdeq_opos_t)(-1))

#define XDEQ_PPTR(xdeq_this, xmap_cpos) ((xdeq_this)->xmap_pptr + (xmap_cpos))

#define XDEQ_CPTR(xdeq_this, xmap_cpos) ((xdeq_this)->xmap_pptr[(xmap_cpos)])

#define XDEQ_NPTR(xdeq_this, xmap_cpos, xmap_npos)                      \
    ((xdeq_nptr_t)(((xstd_bptr_t)XDEQ_CPTR((xdeq_this), (xmap_cpos))) + \
                   ((xmap_npos) * XDEQ_ESIZE(xdeq_this))))

#define XDEQ_CHUNK_MSIZE(xdeq_this) \
    ((xdeq_this)->xchk_size * XDEQ_ESIZE(xdeq_this))

#define XDEQ_CHUNK_COUNT(xdeq_this, xdeq_opos, xdeq_size)   \
    ((XDEQ_NPOS((xdeq_this), (xdeq_opos)) +                 \
      (xdeq_size) + ((xdeq_this)->xchk_size - 1)) / (xdeq_this)->xchk_size)

#define XDEQ_CHUNK_USED(xdeq_this)              \
    XDEQ_CHUNK_COUNT((xdeq_this),               \
                     (xdeq_this)->xmap_bpos,    \
                     (xdeq_this)->xdeq_size)

#define XDEQ_ELEM(xdeq_this, xdeq_opos)             \
    XDEQ_NPTR((xdeq_this),                          \
              XDEQ_CPOS((xdeq_this), (xdeq_opos)),  \
              XDEQ_NPOS((xdeq_this), (xdeq_opos)))

#define XDEQ_FRONT(xdeq_this) XDEQ_ELEM((xdeq_this), XDEQ_BEGIN(xdeq_this))
#define XDEQ_BACK(xdeq_this)  XDEQ_ELEM((xdeq_this), XDEQ_RBEGIN(xdeq_this))

#define XDEQ_ITER_CAST(xdeq_ctype_t, xdeq_value)  ((xdeq_ctype_t)(xdeq_value))

#define XDEQ_CNP_NEXT(xdeq_this, xdeq_cpos, xdeq_npos)      \
    do                                                      \
    {                                                       \
        if (++(xdeq_npos) == (xdeq_this)->xchk_size)        \
        {                                                   \
            if (++(xdeq_cpos) == (xdeq_this)->xmap_size)    \
                (xdeq_cpos) = 0;                            \
            (xdeq_npos) = 0;                                \
        }                                                   \
    } while (0)

#define XDEQ_CNP_PREV(xdeq_this, xdeq_cpos, xdeq_npos)      \
    do                                                      \
    {                                                       \
        if ((xdeq_npos)-- == 0)                             \
        {                                                   \
            if ((xdeq_cpos)-- == 0)                         \
                (xdeq_cpos) = (xdeq_this)->xmap_size - 1;   \
            (xdeq_npos) = (xdeq_this)->xchk_size - 1;       \
        }                                                   \
    } while (0)

//====================================================================

////////////////////////////////////////////////////////////////////////////////

#endif // __STD_DEQUE_INL__

